package BinaryTree.栈遍历;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * pop (前后push) res (中push）
 *
 * 前序：中左右
 * --左右换-->
 * 中右左
 * --整体反转-->
 * 后序：左右中
 */
public class 二叉树的后序遍历145 {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        //错1：初时 应该放入root，要不while直接跳过了
        stack.push(root);

        while(!stack.isEmpty()){
            //1 top
            TreeNode top = stack.pop();
            //3 push 先左 后右
            if(top.left != null){
                stack.push(top.left);
            }
            if(top.right != null){
                stack.push(top.right);
            }
            //4 res+
            res.add(top.val);
        }
        //5 反转
        Collections.reverse(res);
        return res;
    }

    @Test
    public void test(){
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        postorderTraversal(t1);
        System.out.println(res);
    }
}
